Batch 2 - Class 37 - Search

• Program the flowchart that you built

• Moscow - 86 - (easy fun) - mom has to toast 3 slices of bread, each side takes 30 seconds and the pan can only hold 2 slices at a time - what is the fastest way to do it (1.5 min)
• Lay out 13 cards from a deck on the table, labeled by their "address". Tell students that they can refer to any card by their address and ask a question. They have to find the king in the pack.
• Let them ask questions - soon, they should start to ask sequentially - Play with 3-4 students
• Now try with 26 cards - the approach should still be sequential
• Ask students how many steps should it take them in the worst case. Answer: n
• Now lay out 13 cards in sorted order. Ask students to query
• Guide them till they start to ask for cards roughly in the middle. Keep track of number of queries
• Do the same with 26 cards
• Discussion: Discuss the method they were using to search. When one has some idea of how items are distributed, a guess or interpolation is made to try to quickly find the desired item. This is a kind of "binary search", which usually describes the technique of determining which half contains the item sought for by looking at the item in the middle. Lead them to the conclusion that they reduce the number of potential options by half at each query, whereas the previous search only reduced the number of options by 1 at each query. Ask them why it works - what's the difference between finding an item in a sorted list vs. finding the item in an unsorted list? The answer is simply that we know a lot about where things are if we know a list is sorted. (Tell them that you will teach them about sorting in a future lesson!) 
• Play the game of Guess Who with 2-3 students
• They should start to again try and cut the data set approximately by half each time
• Ask them why they are doing that?
• How many steps will they need to find the character?
• Discussion: Sorting is one easy way in which options can be cut in half in a computer. Guess Who has another kind of query system which allows options to be cut in half without sorting
• MC Diaries Y1, Chap 9 - Problem 13 - How many squares in the figure (31)

            

• Bring out a dictionary and let students try to find a word (based on query system, not flipping through)
• How many steps should it require? This may be done for 4 items, 8 items, 16 items, 32 items and so on
• Ask kids to guess a number between 0-63. Ask questions of "Is the number at least 32" and so on. Write a 1 for every yes answer and 0 for every no answer. Finally the binary number written should be the number
• Ask kids to explain why
• A fun way to conclude this lesson is to draw a big square on the chalkboard and label it "the desert."  Tell the students that there is a lion loose in the desert, and it's our job to build a fence around it so it doesn't hurt anyone.  We don't want to catch it any other way, since it's a very cranky lion.  How should we do it?  Answer:  build a fence dividing the desert into two halves. The lion is now in one of the halves. Next, build a fence across the half containing the lion, constraining the lion to one quarter of the desert. Continue building fences across the half of the remaining desert containing the lion, until the lion is cornered. (We've assumed the lion can't get out of the desert.) 
• Talk about the notion of halving: This lesson demonstrates that seemingly difficult tasks can be performed efficiently when, at each stage of the pursuit, the problem can be reduced to a problem half the original size. This technique (reducing the problem to one whose "size" is some fraction of the original problem) is used in many computer programs, not just for searching.
• How large a possible space of personalities can be explored through "20 questions"? What kind of questions make sense to ask?
• Can you think of something that requires 100 questions?
• Number of protons. electrons and neutrons in the universe is less than 2^300, so you could search the entire universe in 300 questions. 
• What if in our search we have an option to divide the options into three buckets instead of two?
• Contributed by Avy - If 1-R, 2-T, 3-E, 4-N, then 5-?
• Answer: Y (multiply the number by 4, and take last letter of the resulting number)

• NONE - Enjoy!